/*
https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/
 */
import java.util.ArrayList;
import java.util.List;

public class Solution438 {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length()<p.length()){
            return new ArrayList<>();
        }
        List<Integer> list=new ArrayList<>();
        int[] count=new int[26];
        for (int i=0;i<p.length();i++){
            count[s.charAt(i)-'a']++;
            count[p.charAt(i)-'a']--;
        }
        int d=0;
        for (int i=0;i<26;i++) {
            if (count[i]!=0){
                d++;
            }
        }
        if (d==0){
            list.add(0);
        }
        for (int i=0;i<s.length()-p.length();i++){
            int t1 = count[s.charAt(i) - 'a'];
            if (t1==1){
                d--;
            }else if (t1==0){
                d++;
            }
            count[s.charAt(i)-'a']--;
            int t2 = count[s.charAt(i+p.length())-'a'];
            if (t2==-1){
                d--;
            }else if (t2==0){
                d++;
            }
            count[s.charAt(i+p.length())-'a']++;
            if (d==0){
                list.add(i+1);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(new Solution438().findAnagrams("cbaebabacd","abc"));
    }
}
